Deduplication storage systems reduce physical storage space requirements by replacing duplicate regions of data (e.g., files or portions of files) with references to data already stored. Even though deduplication systems provide substantial compression for data storage enabling substantial storage in a single node, requirements for storage capacity, memory, and throughput can exceed a single node's storage capability. Multi-node deduplication storage systems typically deduplicate storage only within each node. This presents a challenge in that in order to achieve the same deduplication efficiency as a single node system an input data must always be directed to the node that has previously stored a copy of the input data. However, a naïve input data directing strategy can lead to a single node overloading (e.g., all input data going to a node with a very favorable overlap in data so that high storage efficiency is achieved) and/or can lead to inefficient deduplication (e.g., all input data being assigned to the least loaded node at any given time, regardless of past assignments, etc.).